package com.justnow.offer;


import java.util.ArrayList;
import java.util.List;

public class Solution54 {

    int count = 0;
    int result = 0;
    List<Integer> list = new ArrayList<>();
    public int kthLargest01(TreeNode root, int k) {
        inOrder(root);
        int res = 0;
        if (list != null)
            res = list.get(list.size() - k);
        return res;

    }

    public void inOrder(TreeNode root) {
        if (root != null) {
            inOrder(root.left);
            list.add(root.val);
            inOrder(root.right);
        }
    }



    public int kthLargest02(TreeNode root, int k) {
        dfs(root, k);
        return result;
    }

    private void dfs(TreeNode root, int k) {
        if (root.right != null) dfs(root.right, k);
        if (++count == k) {
            result = root.val;
            return;
        }
        if (root.left != null) dfs(root.left, k);
    }


    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node2.right = node3;
        node2.left = node4;
        node3.right = node5;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}